package com.wkr.leetcode;

import java.util.*;

public class Nums {

    /**
     * 返回数组所有可能的子集
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        subsetsDfs(nums, 0, temp, ans);
        return ans;
    }

    private void subsetsDfs(int[] nums, int start, List<Integer> temp, List<List<Integer>> ans) {
        if (start == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[start]);
        subsetsDfs(nums, start + 1, temp, ans);
        temp.remove(temp.size() - 1);
        subsetsDfs(nums, start + 1, temp, ans);
    }

    /**
     * 找出数组中只出现了一次的元素。
     */
    public int singleNumber(int[] nums) {
        Set<Integer> ans = new HashSet<>();
        for (int num : nums) {
            if (!ans.add(num)) {
                ans.remove(num);
            }
        }
        for (int num : ans) {
            return num;
        }
        return -1;
    }

    /**
     * 任何数和 0 做异或运算，结果仍然是原来的数，即 a ^ 0 = a。
     * 任何数和其自身做异或运算，结果是 00，即 a ^ a = 0。
     */
    public int singleNumber2(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

    /**
     * 反转数值
     */
    public int reverseInteger(int x) {
        String numStr = String.valueOf(x);
        Stack<Character> stack = new Stack<>();
        int len = numStr.length();
        if (len == 0) {
            return -1;
        }
        int start = numStr.charAt(0) >= '0' && numStr.charAt(0) <= '9' ? 0 : 1;
        boolean minus = start != 0;
        for (int i = start; i < len; i++) {
            stack.push(numStr.charAt(i));
        }
        StringBuilder ansStr = new StringBuilder(minus ? "-" : "");

        while(!stack.empty()){
            ansStr.append(stack.pop());
        }
        try {
            return Integer.valueOf(ansStr.toString());
        } catch (Exception ignored) {}

        return 0;
    }

    public int reverseInteger2(int x) {
        int ans = 0;
        while (x != 0) {
            // (ans * 10) / 10 其中的ans*10，java虚拟机内部实际上是进行了数值类型提升，即溢出时，用long类型数据暂时存储，
            // 最后通过变窄转换，保留低32位数值得到(ans * 10) / 10 != ans。
            if ((ans * 10) / 10 != ans) {
                ans = 0;
                break;
            }
            ans = ans * 10 + x % 10;
            x = x / 10;
        }
        return ans;
    }

    /**
     * 去除数组中的重复数据，且不要使用额外的数组空间
     *
     * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
     * 输出：5, nums = [0,1,2,3,4]
     * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
     */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        // 新数组下标
        int index = 0;
        // 记录上一次出现的值
        int occurVal = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            if (occurVal != nums[i]) {
                if (index != i) {
                    nums[index] = nums[i];
                }
                occurVal = nums[i];
                index++;
            }
        }
        return index;
    }

    /**
     * 移除元素
     * 输入：nums = [3,2,2,3], val = 3
     * 输出：2, nums = [2,2]
     * 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
     * 例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/remove-element
     */
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        // 新数组下标
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                if (i != index) {
                    nums[index] = nums[i];
                }
                index++;
            }
        }
        return index;
    }


    /**
     * 合并两个有序数组
     *
     * 解法一：先合并再排序
     * 解法二：双指针，copy数组再依次将最小的值填入
     * 解法三：双指针，从后往前
     * 应考虑到有个数组数据没用完，同有序链表合并
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        if (m == 0) {
            System.arraycopy(nums2, 0, nums1,0, nums2.length);
            return;
        }
        int index = m + n - 1;
        // 大的数据从最后塞
        while (index >= 0 && n >= 1 && m >= 1) {
            if (nums2[n - 1] > nums1[m - 1]) {
                nums1[index] = nums2[n - 1];
                n--;
            } else {
                nums1[index] = nums1[m - 1];
                m--;
            }
            index--;
        }
        // 如果数组2没有用完
        while (n >= 1) {
            nums1[index] = nums2[n - 1];
            n--;
            index--;
        }
    }

    /**
     * 数组加一
     */
    public int[] plusOne(int[] digits) {
        int index = digits.length - 1;
        List<Integer> ans = new ArrayList<>();
        boolean carry = false;
        for (int i = index; i >= 0; i--) {
            int temp = digits[index];
            if (index == digits.length - 1) {
                temp++;
            }

            if (carry) {
                temp++;
            }

            if (temp > 9) {
                carry = true;
                ans.add(0);
            } else {
                carry = false;
                ans.add(temp);
            }
            index--;
            if (index < 0) {
                break;
            }
        }
        if (carry) {
            ans.add(1);
        }
        int[] res = new int[ans.size()];
        int id = ans.size() - 1;
        for (int i = 0; i < ans.size(); i++, id--) {
            res[id] = ans.get(i);
        }
        return res;
    }

    public int[] plusOne2(int[] digits) {
        int index = digits.length - 1;
        for (int i = index; i >= 0; i--) {
            digits[i]++;
            if (digits[i] > 9) {
                digits[i] = 0;
            } else {
                return digits;
            }
        }

        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}
